#include <iostream>
#include <vector>
#include <array>
#include "euler/prime_table.hpp"
#include "euler/prime_test.hpp"
#include "euler/fibonacci.hpp"
#include "euler/residue.hpp"
#include "euler/imath.hpp"
#include "euler.h"

BEGIN_PROBLEM(304, solve_problem_304)
	PROBLEM_TITLE("Primonacci")
	PROBLEM_ANSWER("283988410192")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(1)
	PROBLEM_TIME_COMPLEXITY("")
	PROBLEM_SPACE_COMPLEXITY("")
END_PROBLEM()

#if 0
template <typename T>
bool miller_rabin(T n)
{
	// Test the first few small numbers.
	if (n <= 1)
		return false;
	if (n == 2)
		return true;
	if (n % 2 == 0)
		return false;
	if (n < 9)
		return true;
	if (n % 3 == 0 || n % 5 == 0 || n % 7 == 0)
		return false;

	if (n < std::numeric_limits<unsigned int>::max())
		return euler::miller_rabin((unsigned int)n);

	// A table of the candidate witness to test.
	static const unsigned long long threshold[4] = {
		//9080191ULL,
		4759123141ULL,
		2152302898747ULL,
		3474749660383ULL,
		341550071728321LL,
	};
	static const int candidates[4][8] = {
		//{ 31, 73, 0 },
		{ 2, 7, 61, 0 },
		{ 2, 3, 5, 7, 11, 0 },
		{ 2, 3, 5, 7, 11, 13, 0 },
		{ 2, 3, 5, 7, 11, 13, 17, 0 },
	};

	// Find the suitable candidate set.
	int k = 0;
	for (; k < 4 && n >= threshold[k]; ++k);
	assert(k < 4);

	// Decompose n-1 = 2^s * d.
	// Complexity: O(log(2,n))
	int s = 0;
	T d = n - 1;
	while (d % 2 == 0)
	{
		d /= 2;
		++s;
	}

	// Check every potential witness. If any witness fails, n is composite.
	// const unsigned int candidates[3] = { 2, 7, 61 };
	for (int i = 0; candidates[k][i]; i++)
	{
		T a = candidates[k][i];
		if (a >= n)
			continue;

		bool passed = false;

		// Compute x = a^d mod n and check whether x == +/- 1 (mod n).
		euler::residue<T> x = euler::mod(a, n) ^ d;
		if (x == (T)1 || x == n - 1)
			passed = true;

		// Checks if any of (a^d)^2, (a^d)^4, ... == -1 (mod n)
		for (int j = 1; !passed && j < s; j++)
		{
			x *= x;
			if (x == n - 1)
				passed = true;
		}

		// Fails the test
		if (!passed)
			return false;
	}
	return true;
}

// Returns the smallest prime greater than p.
template <typename T>
T next_prime(T p)
{
	if (p < 2)
		return 2;
	for (p += (p % 2 == 0)? 1 : 2; !miller_rabin(p); p += 2);
	return p;
}
#endif

static void solve_problem_304()
{
	const long long M = 1234567891011LL;
	typedef euler::residue<long long,M> value_t;

	// Generate the primes using segmented sieve.
	// Estimate the upper bound by assuming pi(x) = x/ln(x),
	// then dx/dpi(x) ~ ln(x) + 1 + 1/(lnx-1) .
	// This formula tends to overestimate the number of primes, 
	// which is good for sieving.
	long long N = 100000;
	long long LB = 10000000LL*10000000LL;
	long long UB = LB + (long long)(N*(std::log((double)LB)+1+1.0/(std::log((double)LB)+1)));
	std::vector<bool> sieve((size_t)(UB-LB+1), true);
	euler::prime_table<int> bootstrap(euler::isqrt(UB)+1);
	for (auto it = bootstrap.begin(); it != bootstrap.end(); ++it)
	{
		int p = *it;
		for (long long k = (LB+p-1)/p*p; k <= UB; k += p)
			sieve[(size_t)(k-LB)] = false;
	}

	std::vector<long long> primes;
	int cp = 0;
	for (long long i = LB; i <= UB; i++)
	{
		if (sieve[(size_t)(i-LB)])
		{
			primes.push_back(i);
			++cp;
			if (cp >= N)
				break;
			//if (cp % 10000 == 1)
			//	std::cout << "P[" << cp << "] = " << i << std::endl;
		}
	}

	// Compute the sum of Fibonacci.
	// std::cout << "Computing Fibonacci..." << std::endl;
	//euler::fibonacci_iterator<value_t> it;(value_t(0,M), value_t(1,M));
	euler::fibonacci_iterator<value_t> it;
	it += primes[0];
	value_t sum = *it;
	for (int i = 1; i < N; i++)
	{
		std::advance(it, primes[i] - primes[i-1]);
		sum += *it;
	}
	std::cout << sum << std::endl;
}
